package org.chnxi.study.datastructrues.graph;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * 邻接矩阵（二维数组）无向图
 */
public class AdjacencyMatrixDemo {

    public static void main(String[] args) {

        System.out.println("第一张图：");
        int n = 5;
        String[] vertexVal = {"A" , "B" , "C" , "D" , "E"};

        AdjacencyMatrixDemo graph = new AdjacencyMatrixDemo(n);

        for (String val : vertexVal){
            graph.insertVertex(val);
        }

        //A-B A-C B-C B-D B-e
        graph.insertEdge(0 , 1 , 1);
        graph.insertEdge(0 , 2 , 1);
        graph.insertEdge(1 , 2 , 1);
        graph.insertEdge(1 , 3 , 1);
        graph.insertEdge(1 , 4 , 1);

        graph.print();

        System.out.println("深度优先：");
        graph.printDFS();
        System.out.println("广度优先：");
        graph.printByBFS();

        System.out.println("==================================================");

        System.out.println("第二张图：");
        int n2 = 8;
        String[] vertexVal2 = {"1","2","3","4","5","6","7","8"};

        AdjacencyMatrixDemo graph2 = new AdjacencyMatrixDemo(n2);

        for (String val : vertexVal2){
            graph2.insertVertex(val);
        }

        //A-B A-C B-C B-D B-e
        graph2.insertEdge(0 , 1 , 1);
        graph2.insertEdge(0 , 2 , 1);
        graph2.insertEdge(1 , 3 , 1);
        graph2.insertEdge(1 , 4 , 1);
        graph2.insertEdge(3 , 7 , 1);
        graph2.insertEdge(4 , 7 , 1);
        graph2.insertEdge(2 , 5 , 1);
        graph2.insertEdge(6 , 6 , 1);
        graph2.insertEdge(5 , 6 , 1);

        graph2.print();

        System.out.println("深度优先：");
        graph2.printDFS();
        System.out.println("广度优先：");
        graph2.printByBFS();



    }

    private List<String> vertexList;//存储顶点集合

    private int[][] edges;//存储图对应的邻接矩阵

    private int numOfEdges;//表示边的数目

    private boolean[] isVisited;//记录某个顶点是否被访问过

    /**
     * 得到顶点的第一个邻接节点
     * @param index 顶点下标
     * @return 如果存在，返回对应的下标，否则返回-1
     */
    public int getFistNeighbor(int index){
        for (int j = 0; j < vertexList.size(); j++){
            if(edges[index][j] > 0){
                return j;
            }
        }
        return -1;
    }

    /**
     * 根据前一个邻接节点的下标获取下一个邻接节点
     * @param v1 顶点
     * @param v2 邻接节点
     * @return 如果存在，返回对应的下标，否则返回-1
     */
    public int getNextNeighbor(int v1 , int v2){
        for (int j = v2+1; j < vertexList.size(); j++){
            if(edges[v1][j] > 0){
                return j;
            }
        }
        return -1;
    }

    /**
     * 深度优先遍历
     * @param isVisited
     * @param i
     */
    private void printByDFS(boolean[] isVisited , int i){
        //首先我们访问该节点，输出
        System.out.print(getValueByIndex(i) + " -> ");
        //将该节点设置为已经访问过
        isVisited[i] = true;
        //查找i的第一个邻接节点
        int w = getFistNeighbor(i);
        while(w != -1){
            if(!isVisited[w]){
                printByDFS(isVisited , w);
            }else{
                w = getNextNeighbor(i , w);
            }
        }
    }

    /**
     * 对printByDFS进行重载，遍历我们所有的节点
     */
    public void printDFS(){
        isVisited = new boolean[getNumOfEdges()];
        //遍历所有的节点
        for (int i = 0; i< getNumOfVertex(); i++){
            if(!isVisited[i]){
                printByDFS(isVisited , i);
            }
        }
        System.out.println();
    }

    /**
     * 广度优先遍历
     * @param isVisited
     * @param i
     */
    private void printByBFS(boolean[] isVisited , int i){
        int u;//表示队列头节点对应的下标
        int w;//表示邻接节点的下标

        //队列，记录节点访问顺序
        LinkedList queue = new LinkedList();


        System.out.print(getValueByIndex(i)+" -> ");//输出当前节点信息
        isVisited[i] = true; //标记节点访问过
        queue.addLast(i);//将节点加入队列

        while (!queue.isEmpty()){
            //取出队列头节点下标
            u = (Integer) queue.removeFirst();
            //得到第一个邻接节点的下标
            w = getFistNeighbor(u);
            while (w != -1){ //找到了
                if(!isVisited[w]){
                    System.out.print(getValueByIndex(w) + " -> ");
                    isVisited[w] = true;
                    queue.addLast(w);
                }else{
                    w = getNextNeighbor(u , w);
                }

            }
        }
    }

    /**
     * 对printByBFS进行重载，遍历我们所有的节点
     */
    public void printByBFS(){
        isVisited = new boolean[getNumOfEdges()];
        for (int i = 0; i < getNumOfVertex(); i++){
            if(!isVisited[i]){
                printByBFS(isVisited , i);
            }
        }
        System.out.println();
    }

    /**
     * 构造器
     * @param n
     */
    public AdjacencyMatrixDemo(int n){
        edges = new int[n][n];
        vertexList = new ArrayList<String>(n);
        numOfEdges = 0;
        isVisited = new boolean[n];
    }

    public void insertVertex(String vertext){
        this.vertexList.add(vertext);
    }

    /**
     * 添加边
     * @param v1 第一个顶点的下标
     * @param v2 第二个顶点的下标
     * @param weight 权值
     */
    public void insertEdge(int v1 , int v2 , int weight){
        edges[v1][v2] = weight;
        edges[v2][v1] = weight;
        numOfEdges++;
    }

    /**
     * 获取节点个数
     * @return
     */
    public int getNumOfVertex(){
        return vertexList.size();
    }

    /**
     * 获取边的数目
     * @return
     */
    public int getNumOfEdges(){
        return numOfEdges;
    }

    /**
     * 获取节点对应的数据
     * @param idx 数组下标
     * @return
     */
    public String getValueByIndex(int idx){
        return vertexList.get(idx);
    }

    /**
     * 获取两个顶点之前的权值
     * @param v1
     * @param v2
     * @return
     */
    public int getWeight(int v1 , int v2){
        return edges[v1][v2];
    }

    /**
     * 打印输出
     */
    public void print(){
        for (int[] link : edges){
            System.out.println(Arrays.toString(link));
        }
    }


}
